<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
	<head>
		<title>Inter Node Lists</title>
<link href="../docs-assets/Breadcrumbs.css" rel="stylesheet" rev="stylesheet" type="text/css">
		<meta name="viewport" content="width=device-width initial-scale=1">
		<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
		<meta http-equiv="Content-Language" content="en-gb">

<link href="../docs-assets/Contents.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Progress.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Navigation.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Fonts.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Base.css" rel="stylesheet" rev="stylesheet" type="text/css">
<script>
function togglePopup(material_id) {
  var popup = document.getElementById(material_id);
  popup.classList.toggle("show");
}
</script>

<link href="../docs-assets/Popups.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Colours.css" rel="stylesheet" rev="stylesheet" type="text/css">
		
	</head>
	<body class="commentary-font">
		<nav role="navigation">
		<h1><a href="../index.html"><img src="../docs-assets/Inform.png" height=72> </a></h1>
<ul><li><a href="../index.html">home</a></li>
</ul><h2>Compiler</h2><ul>
<li><a href="../structure.html">structure</a></li>
<li><a href="../inbuildn.html">inbuild</a></li>
<li><a href="../inform7n.html">inform7</a></li>
<li><a href="../intern.html">inter</a></li>
<li><a href="../services.html">services</a></li>
<li><a href="../secrets.html">secrets</a></li>
</ul><h2>Other Tools</h2><ul>
<li><a href="../inblorbn.html">inblorb</a></li>
<li><a href="../inform6.html">inform6</a></li>
<li><a href="../inpolicyn.html">inpolicy</a></li>
</ul><h2>Resources</h2><ul>
<li><a href="../extensions.html">extensions</a></li>
<li><a href="../kits.html">kits</a></li>
</ul><h2>Repository</h2><ul>
<li><a href="https://github.com/ganelson/inform"><img src="../docs-assets/github.png" height=0> github</a></li>
</ul><h2>Related Projects</h2><ul>
<li><a href="https://github.com/ganelson/inweb"><img src="../docs-assets/github.png" height=0> inweb</a></li>
<li><a href="https://github.com/ganelson/intest"><img src="../docs-assets/github.png" height=0> intest</a></li>
</ul>
		</nav>
		<main role="main">
		<!-- Weave of 'Inter Node Lists' generated by inweb -->
<div class="breadcrumbs">
    <ul class="crumbs"><li><a href="../index.html">Home</a></li><li><a href="../intern.html">Inter Modules</a></li><li><a href="index.html">bytecode</a></li><li><a href="index.html#2">Chapter 2: The Trees</a></li><li><b>Inter Node Lists</b></li></ul></div>
<p class="purpose">Utility functions to store lists of nodes, either as linked lists or flexibly-sized arrays.</p>

<ul class="toc"><li><a href="2-inl.html#SP1">&#167;1. Unsortable lists</a></li><li><a href="2-inl.html#SP3">&#167;3. Sortable lists</a></li></ul><hr class="tocbar">

<p class="commentary firstcommentary"><a id="SP1" class="paragraph-anchor"></a><b>&#167;1. Unsortable lists.</b>Well, these are short and sweet. An <a href="2-inl.html#SP1" class="internal">inter_node_list</a> is just an efficiently
stored linked list of //inter_tree_node//s.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">typedef</span><span class="plain-syntax"> </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">inter_node_list</span><span class="plain-syntax"> {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="identifier-syntax">linked_list</span><span class="plain-syntax"> *</span><span class="identifier-syntax">the_nodes</span><span class="plain-syntax">; </span><span class="comment-syntax"> of </span><span class="extract"><span class="extract-syntax">inter_tree_node</span></span>
<span class="plain-syntax">    </span><span class="identifier-syntax">CLASS_DEFINITION</span>
<span class="plain-syntax">} </span><span class="reserved-syntax">inter_node_list</span><span class="plain-syntax">;</span>

<span class="reserved-syntax">inter_node_list</span><span class="plain-syntax"> *</span><span class="function-syntax">InterNodeList::new</span><button class="popup" onclick="togglePopup('usagePopup1')"><span class="comment-syntax">?</span><span class="popuptext" id="usagePopup1">Usage of <span class="code-font"><span class="function-syntax">InterNodeList::new</span></span>:<br/>The Warehouse - <a href="2-tw.html#SP10">&#167;10</a><br/>Inter in Binary Files - <a href="3-iibf.html#SP10_1_3_2_4">&#167;10.1.3.2.4</a></span></button><span class="plain-syntax">(</span><span class="reserved-syntax">void</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">inter_node_list</span><span class="plain-syntax"> *</span><span class="identifier-syntax">ifl</span><span class="plain-syntax"> = </span><span class="identifier-syntax">CREATE</span><span class="plain-syntax">(</span><span class="reserved-syntax">inter_node_list</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">ifl</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">the_nodes</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">ifl</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>

<span class="reserved-syntax">void</span><span class="plain-syntax"> </span><span class="function-syntax">InterNodeList::add</span><button class="popup" onclick="togglePopup('usagePopup2')"><span class="comment-syntax">?</span><span class="popuptext" id="usagePopup2">Usage of <span class="code-font"><span class="function-syntax">InterNodeList::add</span></span>:<br/>The Permission Construct - <a href="4-tpc3.html#SP3">&#167;3</a><br/>The PropertyValue Construct - <a href="4-tpc7.html#SP3">&#167;3</a></span></button><span class="plain-syntax">(</span><span class="reserved-syntax">inter_node_list</span><span class="plain-syntax"> *</span><span class="identifier-syntax">FL</span><span class="plain-syntax">, </span><span class="reserved-syntax">inter_tree_node</span><span class="plain-syntax"> *</span><span class="identifier-syntax">F</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">F</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">) </span><span class="identifier-syntax">internal_error</span><span class="plain-syntax">(</span><span class="string-syntax">"linked invalid node"</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">FL</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">) </span><span class="identifier-syntax">internal_error</span><span class="plain-syntax">(</span><span class="string-syntax">"bad node list"</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">FL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">the_nodes</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">) </span><span class="identifier-syntax">FL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">the_nodes</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NEW_LINKED_LIST</span><span class="plain-syntax">(</span><span class="reserved-syntax">inter_tree_node</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">ADD_TO_LINKED_LIST</span><span class="plain-syntax">(</span><span class="identifier-syntax">F</span><span class="plain-syntax">, </span><span class="reserved-syntax">inter_tree_node</span><span class="plain-syntax">, </span><span class="identifier-syntax">FL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">the_nodes</span><span class="plain-syntax">);</span>
<span class="plain-syntax">}</span>
</pre>
<ul class="endnotetexts"><li>The structure inter_node_list is private to this section.</li></ul>
<p class="commentary firstcommentary"><a id="SP2" class="paragraph-anchor"></a><b>&#167;2. </b>We can do two things with these: test them for emptiness, and loop through
them. And that's it.
</p>

<pre class="definitions code-font"><span class="definition-keyword">define</span> <span class="identifier-syntax">LOOP_THROUGH_INTER_NODE_LIST</span><span class="plain-syntax">(</span><span class="identifier-syntax">F</span><span class="plain-syntax">, </span><span class="identifier-syntax">ifl</span><span class="plain-syntax">)</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> ((</span><span class="identifier-syntax">ifl</span><span class="plain-syntax">) &amp;&amp; (</span><span class="identifier-syntax">ifl</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">the_nodes</span><span class="plain-syntax">))</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">LOOP_OVER_LINKED_LIST</span><span class="plain-syntax">(</span><span class="identifier-syntax">F</span><span class="plain-syntax">, </span><span class="reserved-syntax">inter_tree_node</span><span class="plain-syntax">, </span><span class="identifier-syntax">ifl</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">the_nodes</span><span class="plain-syntax">)</span>
</pre>
<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="function-syntax">InterNodeList::empty</span><span class="plain-syntax">(</span><span class="reserved-syntax">inter_node_list</span><span class="plain-syntax"> *</span><span class="identifier-syntax">FL</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">FL</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">) </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">TRUE</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">LinkedLists::len</span><span class="plain-syntax">(</span><span class="identifier-syntax">FL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">the_nodes</span><span class="plain-syntax">) == </span><span class="constant-syntax">0</span><span class="plain-syntax">) </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">TRUE</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">FALSE</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP3" class="paragraph-anchor"></a><b>&#167;3. Sortable lists.</b>Unlike an <a href="2-inl.html#SP1" class="internal">inter_node_list</a>, an <a href="2-inl.html#SP3" class="internal">inter_node_array</a> has entries which are
accessible in O(1) time, and can easily be sorted; but it takes more memory.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">typedef</span><span class="plain-syntax"> </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">inter_node_array</span><span class="plain-syntax"> {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">list_extent</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">list_used</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax"> *</span><span class="identifier-syntax">list</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">CLASS_DEFINITION</span>
<span class="plain-syntax">} </span><span class="reserved-syntax">inter_node_array</span><span class="plain-syntax">;</span>

<span class="reserved-syntax">typedef</span><span class="plain-syntax"> </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax"> {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">sort_key</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">struct</span><span class="plain-syntax"> </span><span class="reserved-syntax">inter_tree_node</span><span class="plain-syntax"> *</span><span class="identifier-syntax">node</span><span class="plain-syntax">;</span>
<span class="plain-syntax">} </span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax">;</span>
</pre>
<ul class="endnotetexts"><li>The structure inter_node_array is private to this section.</li><li>The structure ina_entry is private to this section.</li></ul>
<p class="commentary firstcommentary"><a id="SP4" class="paragraph-anchor"></a><b>&#167;4. </b></p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">inter_node_array</span><span class="plain-syntax"> *</span><span class="function-syntax">InterNodeList::new_array</span><span class="plain-syntax">(</span><span class="reserved-syntax">void</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">inter_node_array</span><span class="plain-syntax"> *</span><span class="identifier-syntax">NL</span><span class="plain-syntax"> = </span><span class="identifier-syntax">CREATE</span><span class="plain-syntax">(</span><span class="reserved-syntax">inter_node_array</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_extent</span><span class="plain-syntax"> = </span><span class="constant-syntax">0</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax"> = </span><span class="constant-syntax">0</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">NL</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>

<span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="function-syntax">InterNodeList::array_len</span><span class="plain-syntax">(</span><span class="reserved-syntax">inter_node_array</span><span class="plain-syntax"> *</span><span class="identifier-syntax">NL</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">NL</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">) </span><span class="identifier-syntax">internal_error</span><span class="plain-syntax">(</span><span class="string-syntax">"null inter_node_array"</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP5" class="paragraph-anchor"></a><b>&#167;5. </b>These are expected to be fairly large, so the capacity starts out at 128 and
quadruples each time this is exhausted:
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">void</span><span class="plain-syntax"> </span><span class="function-syntax">InterNodeList::array_add</span><span class="plain-syntax">(</span><span class="reserved-syntax">inter_node_array</span><span class="plain-syntax"> *</span><span class="identifier-syntax">NL</span><span class="plain-syntax">, </span><span class="reserved-syntax">inter_tree_node</span><span class="plain-syntax"> *</span><span class="identifier-syntax">P</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">NL</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">) </span><span class="identifier-syntax">internal_error</span><span class="plain-syntax">(</span><span class="string-syntax">"null inter_node_array"</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_extent</span><span class="plain-syntax"> == </span><span class="constant-syntax">0</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_extent</span><span class="plain-syntax"> = </span><span class="constant-syntax">256</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list</span><span class="plain-syntax"> = (</span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax"> *)</span>
<span class="plain-syntax">            (</span><span class="identifier-syntax">Memory::calloc</span><span class="plain-syntax">(</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_extent</span><span class="plain-syntax">, </span><span class="reserved-syntax">sizeof</span><span class="plain-syntax">(</span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax">), </span><span class="constant-syntax">TREE_LIST_MREASON</span><span class="plain-syntax">));</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax"> &gt;= </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_extent</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">old_extent</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_extent</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_extent</span><span class="plain-syntax"> *= </span><span class="constant-syntax">4</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax"> *</span><span class="identifier-syntax">new_list</span><span class="plain-syntax"> = (</span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax"> *)</span>
<span class="plain-syntax">            (</span><span class="identifier-syntax">Memory::calloc</span><span class="plain-syntax">(</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_extent</span><span class="plain-syntax">, </span><span class="reserved-syntax">sizeof</span><span class="plain-syntax">(</span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax">), </span><span class="constant-syntax">TREE_LIST_MREASON</span><span class="plain-syntax">));</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">i</span><span class="plain-syntax">=0; </span><span class="identifier-syntax">i</span><span class="function-syntax">&lt;NL-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax">; </span><span class="identifier-syntax">i</span><span class="plain-syntax">++)</span>
<span class="plain-syntax">            </span><span class="identifier-syntax">new_list</span><span class="plain-syntax">[</span><span class="identifier-syntax">i</span><span class="plain-syntax">] = </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list</span><span class="plain-syntax">[</span><span class="identifier-syntax">i</span><span class="plain-syntax">];</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">Memory::I7_free</span><span class="plain-syntax">(</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list</span><span class="plain-syntax">, </span><span class="constant-syntax">TREE_LIST_MREASON</span><span class="plain-syntax">, </span><span class="identifier-syntax">old_extent</span><span class="plain-syntax">);</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list</span><span class="plain-syntax"> = </span><span class="identifier-syntax">new_list</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list</span><span class="plain-syntax">[</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax">].</span><span class="element-syntax">sort_key</span><span class="plain-syntax"> = </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list</span><span class="plain-syntax">[</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax">++].</span><span class="element-syntax">node</span><span class="plain-syntax"> = </span><span class="identifier-syntax">P</span><span class="plain-syntax">;</span>
<span class="plain-syntax">}</span>
</pre>
<p class="commentary firstcommentary"><a id="SP6" class="paragraph-anchor"></a><b>&#167;6. </b>Note that this defers to the sorting method supplied in <span class="extract"><span class="extract-syntax">cmp</span></span>; that might
choose to use the <span class="extract"><span class="extract-syntax">sort_key</span></span> value, or might not. <span class="extract"><span class="extract-syntax">sort_key</span></span> is initialised to
be the original position in the array, because that can then be used as a last
resort to ensure that the sorting algorithm is stable; most implementations
of <span class="extract"><span class="extract-syntax">qsort</span></span> in the C standard library are variations on quicksort and are unstable.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">void</span><span class="plain-syntax"> </span><span class="function-syntax">InterNodeList::array_sort</span><span class="plain-syntax">(</span><span class="reserved-syntax">inter_node_array</span><span class="plain-syntax"> *</span><span class="identifier-syntax">NL</span><span class="plain-syntax">,</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">int</span><span class="plain-syntax"> (*</span><span class="identifier-syntax">cmp</span><span class="plain-syntax">)(</span><span class="reserved-syntax">const</span><span class="plain-syntax"> </span><span class="reserved-syntax">void</span><span class="plain-syntax"> *, </span><span class="reserved-syntax">const</span><span class="plain-syntax"> </span><span class="reserved-syntax">void</span><span class="plain-syntax"> *)) {</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">NL</span><span class="plain-syntax"> == </span><span class="identifier-syntax">NULL</span><span class="plain-syntax">) </span><span class="identifier-syntax">internal_error</span><span class="plain-syntax">(</span><span class="string-syntax">"null inter_node_array"</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax"> &gt; </span><span class="constant-syntax">0</span><span class="plain-syntax">)</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">qsort</span><span class="plain-syntax">(</span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list</span><span class="plain-syntax">, (</span><span class="identifier-syntax">size_t</span><span class="plain-syntax">) </span><span class="identifier-syntax">NL</span><span class="plain-syntax">-&gt;</span><span class="element-syntax">list_used</span><span class="plain-syntax">, </span><span class="reserved-syntax">sizeof</span><span class="plain-syntax">(</span><span class="reserved-syntax">ina_entry</span><span class="plain-syntax">), </span><span class="identifier-syntax">cmp</span><span class="plain-syntax">);</span>
<span class="plain-syntax">}</span>
</pre>
<nav role="progress"><div class="progresscontainer">
    <ul class="progressbar"><li class="progressprev"><a href="2-pck.html">&#10094;</a></li><li class="progresschapter"><a href="P-wtmd.html">P</a></li><li class="progresschapter"><a href="1-bm.html">1</a></li><li class="progresscurrentchapter">2</li><li class="progresssection"><a href="2-it.html">it</a></li><li class="progresssection"><a href="2-in.html">in</a></li><li class="progresssection"><a href="2-bkm.html">bkm</a></li><li class="progresssection"><a href="2-np.html">np</a></li><li class="progresssection"><a href="2-tw.html">tw</a></li><li class="progresssection"><a href="2-pck.html">pck</a></li><li class="progresscurrent">inl</li><li class="progresssection"><a href="2-st.html">st</a></li><li class="progresssection"><a href="2-sym.html">sym</a></li><li class="progresssection"><a href="2-ann.html">ann</a></li><li class="progresssection"><a href="2-tw2.html">tw2</a></li><li class="progresssection"><a href="2-trn.html">trn</a></li><li class="progresschapter"><a href="3-ic.html">3</a></li><li class="progresschapter"><a href="4-tcc.html">4</a></li><li class="progresschapter"><a href="5-tac.html">5</a></li><li class="progresschapter"><a href="6-tpc.html">6</a></li><li class="progressnext"><a href="2-st.html">&#10095;</a></li></ul></div>
</nav><!-- End of weave -->

		</main>
	</body>
</html>

